package 力扣.二分;

public class 数组中数值和下标相等的元素 {
    /**
     * 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
     * 请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
     *
     * 例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。
     * 样例
     * 输入：[-3, -1, 1, 3, 5]
     * 输出：3
     * 注意:如果不存在，则返回-1。
     */
    /**
     * 数组单调递增：说明可以用二分
     * @param nums
     * @return
     */
    public int getNumberSameAsIndex(int[] nums) {
        if (nums == null || nums.length == 0){
            return  -1;
        }
        int N = nums.length;
        return binSearch(nums,0,N);
    }

    private int binSearch(int[] nums, int i, int n) {
        int l = i,r = n;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (nums[m] < m){
                l = m + 1;
            }else if (nums[m] == m){
                return nums[m];
            }else{
                r = m;
            }
        }
        return -1;
    }
}
